package dzz.Week1;

import java.util.*;

/**
 * @author dzz
 */
public class JianZhiOffer58_FlipWordOrder {

    class SolutionFor {
        public String reverseWords(String s) {
            String[] words = s.split("\\s+");
            int wordLength = words.length;
            String reverseWord = "";
            for (int i = 1; i <= wordLength; i++) {
                reverseWord = reverseWord + words[wordLength - i] + "\\s+";
            }
            return reverseWord;
        }
    }

    class SolutionrReverse {
        public String reverseWords(String s) {
            // 除去开头和末尾的空白字符串
            s = s.trim();
            // 正则匹配连续的空白字符作为分隔符分割
            List<String> wordList = Arrays.asList(s.split("\\s+"));
            Collections.reverse(wordList);
            return String.join(" ", wordList);
        }
    }

    // todo 还有两种题解，明天提交
    class Solution {
        public String reverseWords(String s) {
            StringBuilder sb = trimSpaces(s);

            // 翻转字符串
            reverse(sb, 0, sb.length() -1);

            // 翻转每个单词
            reverseEachWord(sb);

            return sb.toString();
        }

        public StringBuilder trimSpaces(String s) {
            int left = 0 , right = s.length() - 1;
            // 去除字符串开头的空白字符串
            while (left <= right && "".equals(s.charAt(left))) {
                ++ left;
            }

            // 去除字符串末尾的空白字符串
            while (left <= right && "".equals(s.charAt(right))) {
                --right;
            }

            // 将字符串间多余的空白字符去除
            StringBuilder sb = new StringBuilder();
            while (left <= right) {
                char c = s.charAt(left);

                if (!"".equals(c) ) {
                    sb.append(c);
                } else if (!"".equals(sb.charAt(sb.length() -1))) {
                    sb.append(c);
                }
                ++left;
            }
            return sb;
        }

        public void reverse(StringBuilder sb, int left, int right) {
            while (left < right) {
                char tmp = sb.charAt(left);
                sb.setCharAt(left++, sb.charAt(right));
                sb.setCharAt(right--, tmp);
            }
        }

        public void reverseEachWord(StringBuilder sb) {
            int n = sb.length();
            int start = 0, end = 0;

            while (start < n) {
                // 循环至单词的末尾
                while (end < n && (!"".equals(sb.charAt(end)))) {
                    ++ end;
                }
                // 翻转单词
                reverse(sb, start, end -1);
                // 更新 start, 去找下一个单词
                start = end + 1;
                ++ end;
            }
        }
    }

    class SolutionTwo {
        public String reverseWords(String s) {
            int left  = 0, right = s.length() -1;
            // 去字符串开头的空白字符
            while (left <= right && "".equals(s.charAt(left)) ) {
                ++ left;
            }

            // 去除字符串末尾的空白字符
            while (left <= right && "".equals(s.charAt(right))) {
                -- right;
            }

            Deque<String> d = new ArrayDeque<>();
            StringBuilder word = new StringBuilder();

            while (left <= right) {
                char c = s.charAt(left);
                if ((word.length() != 0) && ("".equals(c))) {
                    // 将单词push到队列的头部
                    d.offerFirst(word.toString());
                    word.setLength(0);
                } else if (!"".equals(c)) {
                    word.append(c);
                }
                ++ left;
            }
            d.offerFirst(word.toString());

            return String.join("", d);
        }

    }

}
